1. Technical Field
The invention disclosed broadly relates to a data processing technology and more particularly relates to improvements in arithmetic circuitry especially for the generation of parity bit values.
2. Background Art
The practice of producing a parity bit to be associated with a byte or multiple byte expression of a numeric value is well-known in the art, and is used as a means to insure that single bit errors which occur in the byte or multiple byte expression can be detected and with appropriate circuitry, corrected. The production of a parity bit finds its best use in the detection of errors which occur during the transmission of a byte or multiple byte expression over a communications medium. Conventionally, parity can be considered as either even parity or odd parity. Odd parity is defined herein as a binary bit P having a value of one when the byte or multiple byte expression with which it is associated has an odd number of ones contained therein. Even parity is by definition herein the binary value of a parity bit P.sub.e =1 when there are an even number of ones in the byte or multiple byte expression associated therewith. For uniformity of discussion herein, odd parity will be employed as the form of parity to be discussed. The choice of even or add parity is merely a local convention, either choice providing essentially the same results.
In the prior art, the classic technique for generating the parity of a sum output of an N bit adder is to apply the N bits of the sum output to an N bit exclusive OR (in reality an exclusive OR tree) so as to produce a single binary bit for the odd parity value associated with the N bit sum. The problem in the prior art of producing parity in this classical manner is the duration required, since one must wait for the carry bit to propagate over all of the N bits producing the N bit sum, in order to be able to apply all N bits to the N bit input of the exclusive OR parity generator. A number of techniques have been attempted in the prior art to reduce the duration necessary to compute the parity of the sum output of an N bit adder. However all have failed in either requiring extensive logic and therefore a large area to occupy on an integrated circuit chip in order to embody a complex logic function which is sufficiently fast or else they suffer relatively slow operation because of the number of logic delays necessary to generate sufficient information to establish the parity value.